/*
 * 0060. 搜索插入位置
 * 给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
 * 你可以假设在数组中无重复元素。
 * https://www.lintcode.com/problem/search-insert-position/description
 * 
 * 样例
 * [1,3,5,6]，5 → 2
 * [1,3,5,6]，2 → 1
 * [1,3,5,6]， 7 → 4
 * [1,3,5,6]，0 → 0
 * 
 * 挑战
 * O(log(n)) time
 * 
 * 2018.07.13 @jeyming
 */

public class L0060_Search_insert_position {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: An integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
    	if((A.length == 0) || (target <= A[0])) {
    		return 0;
    	} else if(target > A[A.length - 1]) {
    		return A.length;
    	} else if(target == A[A.length - 1]) {
    		return A.length - 1;
    	} else {
//    		for(int i = 0; i < A.length - 2; ++i) {
//    			if(A[i] == target) {
//    				return i;
//    			} 
//    			if((A[i] < target) && (A[i + 1] > target)){
//    				return i + 1;
//    			}
//    		}
    		//方法二：结合二分查找法查找
    		int index = 0;
    		int lastindex = A.length - 1;
    		while(index != lastindex) {
    			int middle = (index + lastindex) / 2;
    			if(A[middle] > target) {
    				lastindex = middle;
    			} else if(A[middle] < target) {
    				index = middle;
    			} else {
    				return middle;
    			}
    			if(lastindex - index == 1) {
    				return index + 1;
    			}
    		}
    	}
    	return 0;
    }

	/**
	 * @param A: an integer sorted array
	 * @param target: an integer to be inserted
	 * @return: An integer
	 */
	public int searchInsert2(int[] A, int target) {
		// write your code here
		for (int i = 0; i < A.length; ++i) {
			if (A[i] == target || A[i] > target) {
				return i;
			}
		}
		return A.length;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
